﻿/**
 * @file fs.c
 * @date 23.5.6
 * @author yrz
 * @brief 文件系统实现，包含五个方面
 * @brief 1.块：磁盘块的分配
 * @brief 2.日志：多步更新时的崩溃恢复
 * @brief 3.文件：索引节点分配、文件读写、元数据
 * @brief 4.目录：有其他inode列表的索引节点
 * @brief 5.名字：文件的路径名，如/home/yrz/pro/fs.c
 * @version 0.1
 * @status Stable

**/



#include "types.h"
#include "riscv.h"
#include "defs.h"
#include "param.h"
#include "stat.h"
//#include "spinlock.h"
#include "proc.h"
//#include "sleeplock.h"
#include "fs.h"
#include "buf.h"
#include "file.h"

#define min(a, b) ((a) < (b) ? (a) : (b))

struct superblock sb;


/**
 * @brief 读取超级块
 * @param dev 设备号
 * @param sb 超级块指针 
*/
static void
readsb(int dev, struct superblock* sb)
{
    struct buf* bp;

    bp = bread(dev, 1);
    //将bp读取的字符串移动到sb中
    memmove(sb, bp->data, sizeof(*sb));
    brelse(bp);
}



/**
 * @brief 初始化文件系统
 * @param dev 设备号
*/
void
fsinit(int dev) {
    readsb(dev, &sb);
    if (sb.magic != FSMAGIC)
        panic("invalid file system");
    initlog(dev, &sb);
}

/**
 * @brief 清空块
 * @param dev 设备号
 * @param bno 块号
*/
static void
bzero(int dev, int bno)
{
    struct buf* bp;

    bp = bread(dev, bno);
    memset(bp->data, 0, BSIZE);
    log_write(bp);
    brelse(bp);
}

// Blocks.


/**
 * @brief 分配初始化为0的磁盘块
 * @param dev 设备号
 * @return 超过磁盘空间则返回0，否则返回分配的空间大小
*/
static uint
balloc(uint dev)
{
    int b, bi, m;
    struct buf* bp;

    bp = 0;
    for (b = 0; b < sb.size; b += BPB) {
        bp = bread(dev, BBLOCK(b, sb));
        for (bi = 0; bi < BPB && b + bi < sb.size; bi++) {
            m = 1 << (bi % 8);
            if ((bp->data[bi / 8] & m) == 0) {  // 块是否空闲
                bp->data[bi / 8] |= m;  // 将块设为使用中.
                log_write(bp);
                brelse(bp);
                bzero(dev, b + bi);
                return b + bi;
            }
        }
        brelse(bp);
    }
    printf("balloc: out of blocks\n");
    return 0;
}

/**
 * @brief 释放磁盘块
 * @param dev 设备号
 * @param b 块号
*/
static void
bfree(int dev, uint b)
{
    struct buf* bp;
    int bi, m;

    bp = bread(dev, BBLOCK(b, sb));
    bi = b % BPB;
    m = 1 << (bi % 8);
    if ((bp->data[bi / 8] & m) == 0)
        panic("freeing free block");
    bp->data[bi / 8] &= ~m;
    log_write(bp);
    brelse(bp);
}



//索引节点表
struct {
    //struct spinlock lock;
    struct inode inode[NINODE];
} itable;

void
iinit()
{
    int i = 0;

    //initlock(&itable.lock, "itable");
    for (i = 0; i < NINODE; i++) {
        //initsleeplock(&itable.inode[i].lock, "inode");
    }
}

static struct inode* iget(uint dev, uint inum);


/**
 * @brief 分配一个索引节点
 * @param dev 设备号
 * @param type 文件类型
 * @return 索引节点指针，没有空闲索引节点则返回NULL
*/
struct inode*
ialloc(uint dev, short type)
{
    int inum;
    struct buf* bp;
    struct dinode* dip;

    for (inum = 1; inum < sb.ninodes; inum++) {
        bp = bread(dev, IBLOCK(inum, sb));
        dip = (struct dinode*)bp->data + inum % IPB;
        if (dip->type == 0) {  // 空闲索引节点
            memset(dip, 0, sizeof(*dip));
            dip->type = type;
            log_write(bp);   // mark it allocated on the disk
            brelse(bp);
            return iget(dev, inum);
        }
        brelse(bp);
    }
    printf("ialloc: no inodes\n");
    return 0;
}


/**
 * @brief 将修改后的索引拷贝到磁盘
 * @param ip 索引节点指针
*/
void
iupdate(struct inode* ip)
{
    struct buf* bp;
    struct dinode* dip;

    bp = bread(ip->dev, IBLOCK(ip->inum, sb));
    dip = (struct dinode*)bp->data + ip->inum % IPB;
    dip->type = ip->type;
    dip->major = ip->major;
    dip->minor = ip->minor;
    dip->nlink = ip->nlink;
    dip->size = ip->size;
    memmove(dip->addrs, ip->addrs, sizeof(ip->addrs));
    log_write(bp);
    brelse(bp);
}


/**
 * @brief 找到设备号为dev、索引节点号为inum的索引节点
 * @param dev 设备号
 * @param inum 索引号
 * @return 索引节点指针
*/
static struct inode*
iget(uint dev, uint inum)
{
    struct inode* ip, * empty;

    //acquire(&itable.lock);

    // 索引节点是否已经在表中
    empty = 0;
    for (ip = &itable.inode[0]; ip < &itable.inode[NINODE]; ip++) {
        if (ip->ref > 0 && ip->dev == dev && ip->inum == inum) {
            ip->ref++;
            // release(&itable.lock);
            return ip;
        }
        if (empty == 0 && ip->ref == 0)    // 记忆空的槽.
            empty = ip;
    }

    // 回收一个inode条目.
    if (empty == 0)
        panic("iget: no inodes");

    ip = empty;
    ip->dev = dev;
    ip->inum = inum;
    ip->ref = 1;
    ip->valid = 0;
    //release(&itable.lock);

    return ip;
}


/**
 * @brief 引用数加1
 * @param ip 索引节点
 * @return 索引节点
*/
struct inode*
idup(struct inode* ip)
{
    //acquire(&itable.lock);
    ip->ref++;
    //release(&itable.lock);
    return ip;
}

// Lock the given inode.
// Reads the inode from disk if necessary.

void
ilock(struct inode* ip)
{
    struct buf* bp;
    struct dinode* dip;

    if (ip == 0 || ip->ref < 1)
        panic("ilock");

    //acquiresleep(&ip->lock);

    if (ip->valid == 0) {
        bp = bread(ip->dev, IBLOCK(ip->inum, sb));
        dip = (struct dinode*)bp->data + ip->inum % IPB;
        ip->type = dip->type;
        ip->major = dip->major;
        ip->minor = dip->minor;
        ip->nlink = dip->nlink;
        ip->size = dip->size;
        memmove(ip->addrs, dip->addrs, sizeof(ip->addrs));
        brelse(bp);
        ip->valid = 1;
        if (ip->type == 0)
            panic("ilock: no type");
    }
}

// Unlock the given inode.

void
iunlock(struct inode* ip)
{
    if (ip == 0 ||  ip->ref < 1)
        panic("iunlock");

    //releasesleep(&ip->lock);
}



void
iput(struct inode* ip)
{
    //acquire(&itable.lock);

    if (ip->ref == 1 && ip->valid && ip->nlink == 0) {
        // 索引节点没有其他引用了：截断并释放.


        //acquiresleep(&ip->lock);

        //release(&itable.lock);

        itrunc(ip);
        ip->type = 0;
        iupdate(ip);
        ip->valid = 0;

        //releasesleep(&ip->lock);

        //acquire(&itable.lock);
    }

    ip->ref--;
    //release(&itable.lock);
}

// Common idiom: unlock, then put.
void
iunlockput(struct inode* ip)
{
    iunlock(ip);
    iput(ip);
}

// Inode content
//

/**
 * @brief 查找某个索引节点的某个块的地址
 * @param ip 索引节点
 * @param bn 块号
 * @return 块地址
*/
static uint
bmap(struct inode* ip, uint bn)
{
    uint addr, * a;
    struct buf* bp;

    if (bn < NDIRECT) {
        if ((addr = ip->addrs[bn]) == 0) {
            addr = balloc(ip->dev);
            if (addr == 0)
                return 0;
            ip->addrs[bn] = addr;
        }
        return addr;
    }
    bn -= NDIRECT;

    if (bn < NINDIRECT) {
        // Load indirect block, allocating if necessary.
        if ((addr = ip->addrs[NDIRECT]) == 0) {
            addr = balloc(ip->dev);
            if (addr == 0)
                return 0;
            ip->addrs[NDIRECT] = addr;
        }
        bp = bread(ip->dev, addr);
        a = (uint*)bp->data;
        if ((addr = a[bn]) == 0) {
            addr = balloc(ip->dev);
            if (addr) {
                a[bn] = addr;
                log_write(bp);
            }
        }
        brelse(bp);
        return addr;
    }

    panic("bmap: out of range");
}


/**
 * @brief 截断索引节点(丢弃内容)
 * @param ip 索引节点
*/
void
itrunc(struct inode* ip)
{
    int i, j;
    struct buf* bp;
    uint* a;

    for (i = 0; i < NDIRECT; i++) {
        if (ip->addrs[i]) {
            bfree(ip->dev, ip->addrs[i]);
            ip->addrs[i] = 0;
        }
    }

    if (ip->addrs[NDIRECT]) {
        bp = bread(ip->dev, ip->addrs[NDIRECT]);
        a = (uint*)bp->data;
        for (j = 0; j < NINDIRECT; j++) {
            if (a[j])
                bfree(ip->dev, a[j]);
        }
        brelse(bp);
        bfree(ip->dev, ip->addrs[NDIRECT]);
        ip->addrs[NDIRECT] = 0;
    }

    ip->size = 0;
    iupdate(ip);
}


/**
 * @brief 拷贝索引节点的stat信息
 * @param ip 索引节点
*/
void
stati(struct inode* ip, struct stat* st)
{
    st->dev = ip->dev;
    st->ino = ip->inum;
    st->type = ip->type;
    st->nlink = ip->nlink;
    st->size = ip->size;
}


/**
 * @brief 读取索引节点的数据
 * @param ip 索引节点
 * @param user_dst 如果为1，dst为用户虚拟地址，否则dst为内核地址
 * @param dst 内核地址或用户虚拟地址
 * @param off 偏移量
 * @param n 读的数据量？
 * @return 成功读取的字节数
*/
int
readi(struct inode* ip, int user_dst, uint64 dst, uint off, uint n)
{
    uint tot, m;
    struct buf* bp;

    if (off > ip->size || off + n < off)
        return 0;
    if (off + n > ip->size)
        n = ip->size - off;

    for (tot = 0; tot < n; tot += m, off += m, dst += m) {
        uint addr = bmap(ip, off / BSIZE);
        if (addr == 0)
            break;
        bp = bread(ip->dev, addr);
        m = min(n - tot, BSIZE - off % BSIZE);
        if (either_copyout(user_dst, dst, bp->data + (off % BSIZE), m) == -1) {
            brelse(bp);
            tot = -1;
            break;
        }
        brelse(bp);
    }
    return tot;
}


/**
 * @brief 将数据写入索引节点
 * @param ip 索引节点
 * @param user_dst 如果为1，dst为用户虚拟地址，否则dst为内核地址
 * @param dst 内核地址或用户虚拟地址
 * @param off 偏移量
 * @param n 写的数据量？
 * @return 成功写的字节数
*/
int
writei(struct inode* ip, int user_src, uint64 src, uint off, uint n)
{
    uint tot, m;
    struct buf* bp;

    if (off > ip->size || off + n < off)
        return -1;
    if (off + n > MAXFILE * BSIZE)
        return -1;

    for (tot = 0; tot < n; tot += m, off += m, src += m) {
        uint addr = bmap(ip, off / BSIZE);
        if (addr == 0)
            break;
        bp = bread(ip->dev, addr);
        m = min(n - tot, BSIZE - off % BSIZE);
        if (either_copyin(bp->data + (off % BSIZE), user_src, src, m) == -1) {
            brelse(bp);
            break;
        }
        log_write(bp);
        brelse(bp);
    }

    if (off > ip->size)
        ip->size = off;


    iupdate(ip);

    return tot;
}

// Directories

int
namecmp(const char* s, const char* t)
{
    return strncmp(s, t, DIRSIZ);
}


/**
 * @brief 查找目录中的目录条目
 * @param dp 目录地址
 * @param name 文件名
 * @param poff 条目的字节偏移

*/
struct inode*
dirlookup(struct inode* dp, char* name, uint* poff)
{
    uint off, inum;
    struct dirent de;

    if (dp->type != T_DIR)
        panic("dirlookup not DIR");

    for (off = 0; off < dp->size; off += sizeof(de)) {
        if (readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
            panic("dirlookup read");
        if (de.inum == 0)
            continue;
        if (namecmp(name, de.name) == 0) {
            // 条目和文件名匹配
            if (poff)
                *poff = off;
            inum = de.inum;
            return iget(dp->dev, inum);
        }
    }

    return 0;
}


/**
 * @brief 写一个新的目录条目
 * @param dp 目录地址
 * @param name 文件名
 * @param inum 条目的索引节点数
 * @return 成功返回0，否则返回-1
*/
int
dirlink(struct inode* dp, char* name, uint inum)
{
    int off;
    struct dirent de;
    struct inode* ip;

    // 检查文件名是否已存在
    if ((ip = dirlookup(dp, name, 0)) != 0) {
        iput(ip);
        return -1;
    }

    // 查找一个空的目录
    for (off = 0; off < dp->size; off += sizeof(de)) {
        if (readi(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
            panic("dirlink read");
        if (de.inum == 0)
            break;
    }

    strncpy(de.name, name, DIRSIZ);
    de.inum = inum;
    if (writei(dp, 0, (uint64)&de, off, sizeof(de)) != sizeof(de))
        return -1;

    return 0;
}

// Paths


/**
 * @brief 将路径名中，name之后的部分提取出。示例：当name=‘a’，skipelem("a/bb/c", name) = "bb/c"
 * @param path 路径名
 * @param name 某级目录名

*/
static char*
skipelem(char* path, char* name)
{
    char* s;
    int len;

    while (*path == '/')
        path++;
    if (*path == 0)
        return 0;
    s = path;
    while (*path != '/' && *path != 0)
        path++;
    len = path - s;
    if (len >= DIRSIZ)
        memmove(name, s, DIRSIZ);
    else {
        memmove(name, s, len);
        name[len] = 0;
    }
    while (*path == '/')
        path++;
    return path;
}


/**
 * @brief 查找路径名对应的索引节点
 * @param path 路径名
 * @param nameiparent 是否有上一级索引节点
 * @param name 文件名
*/
static struct inode*
namex(char* path, int nameiparent, char* name)
{
    struct inode* ip, * next;

    if (*path == '/')
        ip = iget(ROOTDEV, ROOTINO);
    else
        ip = idup(myproc()->cwd);

    while ((path = skipelem(path, name)) != 0) {
        ilock(ip);
        if (ip->type != T_DIR) {
            iunlockput(ip);
            return 0;
        }
        if (nameiparent && *path == '\0') {
            // Stop one level early.
            iunlock(ip);
            return ip;
        }
        if ((next = dirlookup(ip, name, 0)) == 0) {
            iunlockput(ip);
            return 0;
        }
        iunlockput(ip);
        ip = next;
    }
    if (nameiparent) {
        iput(ip);
        return 0;
    }
    return ip;
}

struct inode*
namei(char* path)
{
    char name[DIRSIZ];
    return namex(path, 0, name);
}

struct inode*
nameiparent(char* path, char* name)
{
    return namex(path, 1, name);
}
